package top.minuy.subject.leetcode._980;

/**
 * 记忆化搜索
 *
 * 980. 不同路径 III
 * 在二维网格 grid 上，有 4 种类型的方格：
 * <p>
 * 1 表示起始方格。且只有一个起始方格。
 * 2 表示结束方格，且只有一个结束方格。
 * 0 表示我们可以走过的空方格。
 * -1 表示我们无法跨越的障碍。
 * 返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。
 * <p>
 * 每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
 * 输出：2
 * 解释：我们有以下两条路径：
 * 1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
 * 2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)
 * 示例 2：
 * <p>
 * 输入：[[1,0,0,0],[0,0,0,0],[0,0,0,2]]
 * 输出：4
 * 解释：我们有以下四条路径：
 * 1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
 * 2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
 * 3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
 * 4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)
 * 示例 3：
 * <p>
 * 输入：[[0,1],[2,0]]
 * 输出：0
 * 解释：
 * 没有一条路能完全穿过每一个空的方格一次。
 * 请注意，起始和结束方格可以位于网格中的任意位置。
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= grid.length * grid[0].length <= 20
 * 通过次数14,862提交次数20,189
 *
 *
 * @author Minuy
 * @time 11:03
 * @date 2021/11/23
 */
public class Solution1 {
    int[][] grid; // 格子的引用
    int R, C; // 行数，列数
    int start, end; // 开始位置，结束位置
    int[][] memo; // 记忆数组

    int[][] dir4 = { // 上，下，左，右 4方向变量
            {1,0},
            {0,-1},      {0,1},
            {-1,0}
    };

    public int uniquePathsIII(int[][] grid) {
        this.grid = grid;

        R = grid.length; // 行
        C = grid[0].length; // 列

        int left = 0;
        // 扫描整个地图，判断一共有多少个可以走的格子，获取起点和终点
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (grid[i][j] == 0) {
                    left++;
                } else if (grid[i][j] == 1) {
                    start = i * C + j;left++;
                } else if (grid[i][j] == 2) {
                    end = i * C + j;left++;
                }
            }
        }

        int isVisited = 0;

        memo  = new int[1<<(R*C)][(R*C)]; // 压缩坐标时是对整个格子来讲的
        for (int i=0;i<memo.length;i++){
            for (int j=0;j<memo[0].length;j++){
                memo[i][j]  = -1;
            }
        }

        // 深度优先遍历来获取路径数量
        return dfs(isVisited ,start, left);
    }

    private int dfs(int isVisited,int v, int left) {

        if (memo[isVisited][v] != -1){
            return memo[isVisited][v]; // 直接返回之前的结果
        }

        isVisited+=1<<v;

        left--;

        if (left == 0) {
            // isVisited-=1<<v; // 回溯，给其他路径留活路
            if(v == end) {
                memo[isVisited][v] = 1;
                return 1;
            }
            return 0; // 找到了一条哈密尔顿路径
        }

        int x = v / C;
        int y = v % C;

        int res = 0;
        // 获取相邻顶点
        for (int[] ints : dir4) {
            int x1 = x + ints[0];
            int y1 = y + ints[1];
            int v1 = x1 * C + y1;
            if (x1 >= 0 && y1 >= 0 && x1 < R && y1 < C && grid[x1][y1] != -1 && ((isVisited&1<<v1) == 0)) {
                res += dfs(isVisited,v1, left);
            }
        }

        isVisited-=1<<v;  // 回溯
        memo[isVisited][v] = res;
        return res;
    }

    public static void main(String[] args) {
        int[][] g = {{1,0,0,0},{0,0,0,0},{0,0,2,-1}};
        int[][] g2 = {{-1,0,1,-1},{2,0,0,0}};
        Solution1 solution = new Solution1();
        System.out.println(solution.uniquePathsIII(g));
        System.out.println(solution.uniquePathsIII(g2));
    }
}
